package model;

/**
 *
 * @author Dustin
 */
public class Heap {
    private int heapSize;
    private int deadspaceSize;
    private int[] data;

    /**
     * Zet de size van de data grootte.
     * @param size
     */
    public Heap(int size) {
        data = new int[size + 1];
    }

    /**
     * Geeft de minimum index terug.
     * @return
     */
    public int getMinimum() {
        return data[1];
    }

    public int getSize() {
        return heapSize;
    }

    /**
     * Geeft de linker child van de meegegeven index terug.
     * @param index
     * @return
     */
    private int getLeftChildIndex(int index) {
        return 2 * index;
    }

    /**
     * Geeft de rechter child van de meegegeven index terug.
     * @param index
     * @return
     */
    private int getRightChildIndex(int index) {
        return 2 * index + 1;
    }

    /**
     * Geeft de parent van de meegegeven index terug.
     * @param index
     * @return
     */
    private int getParentIndex(int index) {
        return index / 2;
    }

    /**
     * Geeft de heapdata terug.
     * @return
     */
    public int[] getData() {
        return data;
    }

    /**
     * Kijkt of er nog iets in de heap zit.
     * @return
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }

    /**
     * Kan een getal in de heap stoppen.
     * @param value
     */
    public void insert(int value) {
        if(heapSize < data.length) {
            data[1 + heapSize] = value;
            percolateUp(heapSize++);
            System.out.println("Inserted " + value);
        }
    }

    public void insertInDeadSpace(int value) {
        data[data.length-1-deadspaceSize] = value;
        System.out.println("Inserted " + value + " in dead space at index " + (data.length-1-deadspaceSize));
        deadspaceSize++;
    }

    /**
     * Kijkt of er nog wat in de heap zit.
     * Zo ja, haalt hij de bovenste uit de heap.
     */
    public int removeMinimum() {
        int minimum = data[1];
        data[1] = data[heapSize--];
        percolateDown(1);
        return minimum;
    }

    /**
     * Kijkt of de index(node) goed staat ten opzichte van zijn onderliggende indexes.
     * Mochten ze verkeerd staan kan deze methode ze ook meteen verplaatsen.
     * @param index
     */
    private void percolateUp(int index) {
        if(index > 1) {
            int parentIndex = getParentIndex(index);
            if(data[parentIndex] > data[index]) {
                int temp = data[parentIndex];
                data[parentIndex] = data[index];
                data[index] = temp;
                percolateUp(parentIndex);
            }
        }
    }

    /**
     * Kijkt of de index(node) goed staat ten opzichte van zijn onderliggende indexes.
     * Mochten ze verkeerd staan kan deze methode ze ook meteen verplaatsen.
     * @param index
     */
    private void percolateDown(int index) {
        int temp = data[index];
        for(int childIndex = 0; index * 2 <= heapSize; index = childIndex) {
            childIndex = index * 2;
            if(childIndex < heapSize && data[getLeftChildIndex(index)] > data[getRightChildIndex(index)]) {
                childIndex++;
            }
            if(data[childIndex] < temp) {
                data[index] = data[childIndex];
            } else {
                break;
            }
        }
        data[index] = temp;
    }

    /**
     * Bouwt de heap op volgens het algoritme
     *
     */
    public void buildHeap() {
        for(int i = heapSize / 2; i > 0; i--) {
            percolateDown(i);
        }
        System.out.println("Build heap; root = " + data[1]);
    }

    public void rebuiltHeap() {
        heapSize = deadspaceSize;
        for(int i = 1; i <= heapSize; i++) {
            int tmp = data[i];
            data[i] = data[data.length - deadspaceSize];
            data[data.length - deadspaceSize--] = tmp;
        }
        System.out.println("Rebuilt heap");
    }

    @Override
    public String toString() {
        String toString = "Heap elements: ";
        for(int i = 1; i <= heapSize; i++) {
            toString += data[i] + "-";
        }
        return toString;
    }

    public void printHeap() {
        System.out.println("All elements: " + data[1] + "-" + data[2] + "-" + data[3]);
    }
}
